class Solution {
public:
    int findRadius(vector<int>& houses, vector<int>& heaters) {
        sort(houses.begin(), houses.end());
        sort(heaters.begin(), heaters.end());
        int heater_index = 0;
        vector<int> memo(houses.size(), INT_MAX);
        for (int i = 0; i < houses.size() && heater_index < heaters.size();)
        {
            if(houses[i] > heaters[heater_index])
                heater_index++;
            else
            {
                memo[i] = min(memo[i], heaters[heater_index] - houses[i]);
                i++;
            }
        }
        heater_index = heaters.size() - 1;
        for (int i = houses.size() - 1; i >= 0 && heater_index >= 0;)
        {
            if(houses[i] < heaters[heater_index])
                heater_index--;
            else
            {
                memo[i] = min(memo[i], houses[i] - heaters[heater_index]);
                i--;
            }
        }
        return *max_element(memo.begin(), memo.end());
    }
};
